package com.py.custom.tms.application.atomic.link;

import java.util.List;

/**
 * description：
 * 删除链表中等于给定值 val 的所有节点。
 *
 * @author pengyou
 * @version 1.0.0
 * @date 2022/4/9
 */
public class ListNodeOp {

    public static void main(String[] args) {
        ListNode intersection = new ListNode(0);
        ListNode head =
                new ListNode(1,
                        new ListNode(2,
                                new ListNode(3,
                                        new ListNode(4,
                                                new ListNode(5,
                                                        new ListNode(6,
                                                                new ListNode(7,
                                                                        intersection)))))));
        ListNode head2 =
                new ListNode(7,
                        new ListNode(7,
                                new ListNode(7,
                                        new ListNode(7,
                                                intersection))));

        ListNode pre = new ListNode(2);
        ListNode cur = new ListNode(3);
        ListNode tail = new ListNode(0);
        pre.next = cur;
        cur.next = tail;
        tail.next = pre;

        ListNode head3 = new ListNode(1, new ListNode(0, new ListNode(0, pre)));

        ListNode listNode2 = detectCycle(head3);
        System.out.println("listNode2 = " + listNode2);

        ListNode intersectionNode = getIntersectionNode(head, head2);
        System.out.println("intersectionNode = " + intersectionNode);

        ListNode listNode1 = removeNthFromEnd(head, 7);
        System.out.println("listNode1 = " + listNode1);

        ListNode listNode = swapPairs(head);
        System.out.println("listNode = " + listNode);

        int val = 6;
        System.out.println("removeElements(head, val) = " + removeElements(head, val));
        System.out.println("removeElements(head, val) = " + removeElements(head2, 7));
    }

    /**
     * 移除相等的 所有元素
     *
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode current = pre.next;
        while (current != null) {
            if (current.value == val) {
                pre.next = current.next;
            } else {
                pre = current;
            }
            current = current.next;
        }
        return dummy.next;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 两两交换
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode none = new ListNode(-1, head);
        ListNode pre = none;
        ListNode cur = head;
        while (cur.next != null && cur.next.next != null) {
            ListNode temp = cur.next.next;
            pre.next = cur.next;
            pre.next.next = cur;
            pre.next.next.next = temp;
            pre = cur;
            cur = temp;
        }
        return none.next;
    }

    /**
     * 移除倒数第n个
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode none = new ListNode(-1, head);
        ListNode fast = none;
        ListNode slow = none;

        for (int i = 0; i < n + 1; i++) {
            if (fast == null) {
                throw new RuntimeException();
            }
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return none.next;
    }

    /**
     * 求两个相交链表的交点
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) {
            return null;
        }

        ListNode curA = headA;
        ListNode curB = headB;

        int lenA = 0;
        int lenB = 0;

        while (curA != null) {
            lenA++;
            curA = curA.next;
        }

        while (curB != null) {
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;

        if (lenA < lenB) {
            int temp = lenA;
            lenA = lenB;
            lenB = temp;
            curA = headB;
            curB = headA;
        }

        int gap = lenA - lenB;
        for (int i = 0; i < gap; i++) {
            curA = curA.next;
        }

        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode index1 = head;
                ListNode index2 = fast;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {

        return null;
    }

    static class ListNode {

        public ListNode() {
        }

        public ListNode(int value) {
            this.value = value;
        }

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }

        int value;
        ListNode next;
    }
}
